import java.util.Arrays;

public class sort {

    /**
     * 直接插入排序
     * 时间复杂度: 最好O(1)
     *           最差O(n^2)
     * 空间复杂度: O(1)
     * 稳定性: 稳定
     * 场景: 元素集合越接近有序,排序的时间效率越高
     */
    public static void insertSort(int[] arr){
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            int cur = arr[i];
            int j;
            for (j = i-1; j >=0 ; j--) {
                if(cur < arr[j]){
                    arr[j+1] = arr[j];
                }else{
                    //arr[j+1] = cur;
                    break;
                }
            }
            arr[j+1] = cur;
        }
    }

    /**
     * 希尔排序(缩小增量排序)(插入排序变形)
     * 时间复杂度 n^1.3 ~ n^1.5
     * 空间复杂度: O(1)
     * 稳定性: 不稳定
     *
     */

    public static void shellSort(int[] arr){
        int gap = arr.length;
        while(gap > 1){
            gap = gap/2;
            shell(arr,gap);
            System.out.println(Arrays.toString(arr));
        }
    }

    public static void shell(int[] arr,int gap){
        for (int i = gap; i < arr.length; i+=gap) {
            int cur = arr[i];
            int j;
            for (j = i-gap; j >=0 ; j-=gap) {
                if(arr[j] > cur){
                    arr[j+gap] = arr[j];
                }else{
                    break;
                }
            }
            arr[j+gap] = cur;
        }
    }

    /**
     * 选择排序(每次选取一个最小的元素记录下来)
     * 时间复杂度: O(n^2)
     * 稳定性: 不稳定
     */
    public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int min = arr[i];
            int minIndex = i;

            for (int j = i+1; j < arr.length; j++) {
                if(arr[j] < min){
                    min = arr[j];
                    minIndex = j;
                }
            }
            arr[minIndex] = arr[i];
            arr[i] = min;
        }
    }

    /**
     * 快速排序(递归)
     * pivot: 基准
     */
    public static void quickSort(int[] arr){
        quick(arr,0,arr.length-1);
    }

    public static void quick(int[] arr,int start,int end){
        if(start>=end) return;
        int pivot = partition3(arr,start,end);
        quick(arr,start,pivot-1);
        quick(arr,pivot+1,end);
    }

    /**
     * 找基准 - Hoare
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int partition(int[] arr, int left, int right) {
        int key = arr[left];
        int i = left;
        while(left < right){
            while(left < right && arr[right] >= key){
                right--;
            }

            while(left < right && arr[left] <= key){
                left++;
            }

            swap(arr,left,right);
        }
        swap(arr,i,left);
        return left;
    }

    /**
     * 挖坑法
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int partition2(int[] arr, int left, int right) {
        int key = arr[left];
        while(left < right){
            while(left < right && arr[right] >= key){
                right--;
            }
            arr[left] = arr[right];

            while(left < right && arr[left] <= key){
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = key;
        return left;
    }

    /**
     * 前后指针法
     * @param arr
     * @param left
     * @param right
     * @return
     */
    private static int partition3(int[] arr, int left, int right) {
        int prev = left;
        int cur = left+1;
        while(cur <= right){
            if(arr[cur] < arr[left] && arr[++prev] != arr[cur]){
                swap(arr,prev,cur);
            }
            cur++;
        }
        swap(arr,left,prev);
        return prev;
    }


    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    /**
     * 归并排序: 采用分治的思想,先分后和
     * 时间复杂度: O(N*logN)
     * 空间复杂度: O(N)
     * 稳定性: 稳定
     * @param
     */

    private static void MergeSort(int[] arr){
        MergeSortFunc(arr,0,arr.length-1);
    }

    public static void MergeSortFunc(int[] arr,int left,int right){
        if(left >= right){
            return;
        }
        int mid = (left+right)/2;

        MergeSortFunc(arr,left,mid);
        MergeSortFunc(arr,mid+1,right);

        // 合并
        Merge(arr,left,right,mid);
    }

    /**
     * 非递归实现
     */
    public static void MergeSortNor(int [] arr ,int left ,int right){
        int gap = 1;
        while(gap < arr.length){
            for (int i = 0; i < arr.length; i+=2*gap) {
                left = i;
                int mid = left+gap-1;
                right = mid+gap;
                if(mid > arr.length){
                    mid = arr.length-1;
                }
                if(right > arr.length){
                    right = arr.length-1;
                }
                Merge(arr,left,right,mid);
            }
            gap*=2;
        }

    }

    private static void Merge(int[] arr, int left, int right, int mid) {
        int s1 = left;
        int s2 = mid+1;
        int[] array = new int[right-left+1];
        int i = 0;
        while(s1<=mid && s2 <= right){
            if(arr[s1] <= arr[s2]){
                array[i] = arr[s1++];
            }else{
                array[i] = arr[s2++];
            }
            i++;
        }

        while(s1 <= mid){
            array[i++] = arr[s1++];
        }

        while(s2 <= right){
            array[i++] = arr[s2++];
        }

        for(i = 0;i<array.length;i++){
            arr[left] =  array[i];
            left++;
        }
    }

    /**
     * 计数排序
     * @param arr
     */
    public static void countSort(int[] arr){
        int minVal = arr[0];
        int maxVal = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] < minVal){
                minVal = arr[i];
            }
            if(arr[i] > maxVal){
                maxVal = arr[i];
            }
        }

        int[] newArr = new int[maxVal-minVal+1];

        for (int i = 0; i < arr.length; i++) {
            newArr[arr[i] - minVal]++;
        }

        int k = 0;
        for (int i = 0; i < newArr.length; i++) {
            while(newArr[i] != 0){
                arr[k++] = i+minVal;
                newArr[i]--;
            }
        }
    }


    public static void main(String[] args) {
        int[] arr = {5,3,1,2,4,7,0,9};
        //insertSort(arr);
        shellSort(arr);
        //selectSort(arr);
        //quickSort(arr);
        //MergeSort(arr);
        //countSort(arr);
        for (int j : arr) {
            System.out.print(j + " ");
        }
    }
}
